This invention relates to a method of computing an image from a computer graphics model described by at least one polygon that is visible in the image.
In known computer graphics models rendering of objects involves processing polygons (usually triangles) and their visual properties. Each polygon covers a number of pixels in the image. The computation of the image involves the determination which pixels are covered by the polygon and the determination of the visual properties of those pixels from the visual properties of the polygon.
A pixel-based algorithm is conceptually the simplest way of performing this computation. In a pixel based algorithm the computation of the visual properties of each pixel is computed independently of the other pixels. In an example of such a pixel based algorithm the polygon is described by the parameters of its edges and a parameterized function that describes its visual appearance as a function of position in the polygon. In this example a measure of the position of each pixel relative (e.g. left/right) to the different edges of the polygon is computed, to determine whether the pixel is inside or outside the polygon. The computation of the visual properties may involve for example computation of the coordinates of the pixel in terms of a reference frame relative to the polygon, to compute the value of the parameterized function at the location of the pixel.
Such a pixel-based algorithm involves a considerable amount of computation. For example, the determination of the position of the pixel relative to an edge involves at least one multiplication for each edge.
Incremental algorithms can reduce the required amount of computation. In an incremental algorithm a major part of the computation is performed once in common for a series of spatially adjacent pixels. Only a relatively small amount of incremental computation is required for each individual pixel. For the determination whether a pixel is inside the polygon for example, the measure of the position relative to an edge can be computed by adding an increment to the corresponding measure for an adjacent pixel. The adjacent pixels are processed successively to allow such reuse of computation results. Similarly, the visual properties can be computed incrementally, from a computation result for an adjacent pixel.
Incremental algorithms are more complicated than pixel-based algorithms. The incremental algorithm involves setting up the parameters for the incremental computation in addition to the actual computation for the pixel. In practical computer graphics systems, such as a PC (Personal Computer) for example, dedicated hardware is provided for performing the incrementing part of the incremental algorithm and a multi-purpose processor could be used to compute the set-up parameters to start the incrementation by the dedicated hardware for a particular polygon. The multi-purpose processor can compute the set-up parameters for a polygon in parallel with the incremental computation of the properties of individual pixels of a previous polygon by the dedicated hardware. Thus very efficient processing of computer graphics can be realized.
Yet there is still a demand to reduce the amount of computation needed for computer graphics. U.S. Pat. No. 5,977,983 for example proposes to reduce the amount of computation at the expense of image quality, with an algorithm that minimizes the loss of image quality. This publication is directed at texture mapping, which involves a perspective transformation of pixel coordinates to coordinates on the surface of a polygon. A perspective transformation requires a lot of computation (typically including a division), but omission of the perspective transformation leads to a deformation of the resulting image. This deformation is smaller for small polygons. According to U.S. Pat. No. 5,977,983 the perspective transformation is omitted for polygons with a size that is below a threshold. Thus, the deformation is minimized because it applies only to the smaller polygons. The threshold is selected interactively so the compromise between computational effort and image quality can be adjusted.
Amongst others, it is an object of the invention to provide for a reduction of the amount of computational effort required for computer graphics that is independent of image quality.
The method according to the invention is described in claim 1. According to the invention small polygons are processed with a pixel-based algorithm, whereas larger polygons are processed with an incremental algorithm. Thus, the computational overhead for initializing update values for use in updating pixel values algorithm is avoided for small polygons, where the number of pixels is so small that reduction in the amount of computation per pixel does not weigh up to this overhead. In that case, a pixel value that would be computed incrementally from a corresponding pixel value for a spatially adjacent pixel if the incremental algorithm were used, is computed individually without updating the corresponding pixel value of the adjacent pixel. The incremental algorithm is only used when it is estimated that the polygon is so large that the incremental algorithm realizes a gain.
In an embodiment of the invention, the incremental algorithm and the pixel-based algorithm are executed with a mutually different first and second processor respectively, so that they can be executed in parallel. Preferably, the second processing circuit that performs the pixel-based algorithm also takes the decision whether a polygon is sufficiently large to use the incremental algorithm and it also computes the set up for the first processing circuit to performs the incremental algorithm. Usually, the first processing circuit is so fast that the processing time depends mainly on the second processing circuit, unless the polygon is very large.
The first processing circuit selects the pixel-based algorithm if the set-up of the incremental algorithm requires more effort than pixel-based computation of all pixels in the polygon (that is, the additional time needed for computing the individual pixels in the scan line-based algorithm is ignored in this case).
Preferably the processing circuit that performs the pixel-based algorithm is a suitably programmed programmable processor and the processing that performs the scan line-based algorithm is a dedicated processor for performing the incremental algorithm.